package A2014;

/*
   今有 100 根绳子，当然会有 200 个绳头。

    如果任意取绳头两两配对，把所有绳头都打结连接起来。最后会形成若干个绳圈（不考虑是否套在一起）。

    我们的问题是：请计算最后将形成多少个绳圈的概率最大？
    
 
本题对数学的推理要求比较高，首先我们要分析，现在有n根绳子，那么任意选取其中两个绳头配对，直到所有绳头均已完成配对，有多少种情况呢？
 
假设n-1根绳子配对完毕共有f(n - 1)种情况，那么在此基础上加一根绳子，重新进行配对，有以下两种情况可以选择：（
1）绳圈个数不变，在n - 1根已配对完毕的绳头中选择一个绳头和当前新添加的一根绳子绳头打结连接起来；
（2）增加一个绳圈，直接让新添加的绳子两个绳头直接相连。
 
所以f(n) = f(n - 1) * (C(1, 2*(n - 1))+ C(0, 2*(n - 1))) = f(n - 1)  * (2*n - 2 + 1) = f(n - 1) * (2*n - 1)
 
有了上述公式，那么可以推导出解决本题的动态转移方程，
f[i][j] = f[i - 1][j] *2 *(i - 1) / (2*i - 1) + f[i - 1][j - 1] * (1) / (2*i - 1)
 
f[i][j]表示当前有i根绳子，形成j个绳圈的概率。（PS：j > i，其概率为0）
 */
public class _7_绳圈 {
	static double[][] f = new double[101][101];

	public static void main(String[] args) {
		f[1][1] = 1;
		for (int i = 2; i <= 100; i++) {
			f[i][1] = (f[i - 1][1] * 2 * (i - 1))/(2*i-1);
			for (int j = 2; j <=i; j++) {
				f[i][j] = (f[i-1][j]*2*(i-1) + f[i - 1][j-1])/(2*i-1);
			}
		}
		double max = -1;
		int pos=0;
		for (int i = 1; i <= 100; i++) {			
			if (max < f[100][i]) {
				max = f[100][i];
				pos=i;
			}
		}
		System.out.println(pos);
	}

}

